package Offer57;

/**
 * @author 23737
 * @time 2021.9.14
 * 和为s的两个数字:输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。
 * 如果有多对数字的和等于s，则输出任意一对即可。
 */
public class Test {
    public static void main(String[] args) {

    }
}

/*使用双循环来进行遍历，是对的但是效率很低，超时了*/
class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[0];
        }
        int[] ints = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int k = target-nums[i];
            for (int j = i+1; j< nums.length; j++) {
                if (nums[j] == k){
                    ints[0] = nums[i];
                    ints[1] = nums[j];
                    return ints;
                }
            }
        }
        return ints;
    }
}

/*用二分来写*/
class SolutionTwo {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            int num = target - nums[i], left = i + 1, right = nums.length - 1;
            if (num <= nums[i]) break;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] == num) return new int[]{nums[i], num};
                else if (nums[mid] > num) right = mid - 1;
                else left = mid + 1;
            }
        }
        return new int[]{};
    }
}


